package d4_sf;

public class Demo3 {
    public static void main(String[] args) {
        //目标: 掌握二分查找算法(相当于一个功能,独立功能,独立成方法)
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};

        //调用方法进行查找
        int index1 = searchDataIndex(arr, 79);
        System.out.println("79的索引是:" + index1);

        //查找不存在的数据
        int index2 = searchDataIndex(arr, 190);
        System.out.println("190的索引是" + index2);
    }


    //二分查找(折半查找)
    public static int searchDataIndex(int[] array, int number) {
        //1、定义头尾指针
        int left = 0;
        int right = array.length - 1;

        //2、循环开始查找(不知道要查找多少次-->用while)
        //结束条件 left <= right
        while(left <= right){
            //3、求取中间值
            int middle = (left + right) / 2;
            //4、用中间位置处的数据跟要查找的数据进行比较
                //判断当前要找的数据, 与中间位置的数据大小情况
            if (number > array[middle]){
                //在右边,left = middle +1
                //往右找  ,左指针更新为 = 中间位置 + 1
                left = middle + 1;
            } else if (number < array[middle]) {
                //在左边, right = middle -1;
                //往左找 , 右指针更新为 = 中间位置 - 1
                right = middle -1;
            }else{
                //找到了,就返回middle
                return middle;
            }
        }
        //最后还是没有找到
        return -1;
    }
}
